import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution438 {
    public List<Integer> findAnagrams(String s, String p) {
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        for(char c: p.toCharArray()){
            need.put(c,need.getOrDefault(c,0) + 1);
        }
        int len = p.length();
        int left = 0,right = 0;
        int vaild = 0;
        List<Integer> res = new ArrayList<>();
        while(right < s.length()){

            char r = s.charAt(right);
            right++;
            //什么时候应该扩大窗口？
            /*当一个元素在need中存在时，将其放进窗口*/
            if(need.containsKey(r)){
                window.put(r,window.getOrDefault(r,0) + 1);
                if (window.get(r).equals(need.get(r))){
                    vaild++;
                }
            }
            //什么时候该缩小窗口？
            /*当窗口大小大于目标子串长度时应该缩小窗口*/
            while (right - left >= len){
                /*什么时候更新结果*/
                if(vaild == need.size()){
                    res.add(left);
                }
                char l = s.charAt(left);
                left++;
                if(need.containsKey(l)){
                    if(need.get(l).equals(window.get(l))){
                        vaild--;
                    }
                    window.put(l,window.getOrDefault(l,0) - 1);
                }
            }
        }
        return res;
    }
}
